#include "Graph.h"
#include <stdlib.h>
#include <string.h>
#include "Stack.h"
#include "Queue.h"

using namespace std;

/* 顶点的访问标志的数组 */
bool visited[MAXVEX];


/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph *Gp)
{
	int i, j, k, w;
	cout << "请输入顶点数和边数（空格分隔）：" << endl;
	cin >> Gp->numNodes >> Gp->numEdges;
	cout << "请输入顶点信息（空格分隔）：" << endl;
	for (i = 0; i < Gp->numNodes; i++)
		cin >> Gp->vexs[i];
	for (i = 0; i < Gp->numNodes; i++)
	{
		for (j = 0; j < Gp->numNodes; j++)
		{
			if (i == j)
				Gp->arc[i][j] = 0;/* 顶点没有到自己的边*/
			else
				Gp->arc[i][j] = INFINITY;/* 邻接矩阵初始化 */
		}
	}

	for (k = 0; k < Gp->numEdges; k++)
	{
		cout << "请输入边（vi, vj)的上标i，下标j和权值w（空格分隔）:" << endl;
		cin >> i >> j >> w;
		Gp->arc[i][j] = w;
		Gp->arc[j][i] = Gp->arc[i][j];/* 因为是无向图，矩阵对称 */
	}
}


void CreateALGraph(GraphAdjList *Gp)
{
	int i, j, k;
	EdgeNode *pe;
	cout << "输入顶点数和边数(空格分隔）:" << endl;
	cin >> Gp->numNodes >> Gp->numEdges;

	for (i = 0 ; i < Gp->numNodes; i++)
	{
		cout << "输入顶点信息：" << endl;
		cin >> Gp->adjList[i].data;
		Gp->adjList[i].firstedge = NULL;/* 将边表置为空表 */
	}

	for (k = 0; k <  Gp->numEdges; k++)/* 建立边表 */
	{
		cout << "输入边(vi,vj)的顶点序号i,j（空格分隔）:" << endl;
		cin >> i >> j;

		/*对称加入i和j的邻接表中。*/
		/* 将pe的指针指向当前顶点上指向的结点 , 即插入到邻接表的最前面，这样不用遍历下去。 */
		pe = (EdgeNode *)malloc(sizeof(EdgeNode));
		pe->adjvex = j;
		pe->next = Gp->adjList[i].firstedge;
		Gp->adjList[i].firstedge = pe;/* 将当前顶点的指针指向pe */

		pe = (EdgeNode *)malloc(sizeof(EdgeNode));
		pe->adjvex = i;
		pe->next = Gp->adjList[j].firstedge;
		Gp->adjList[j].firstedge = pe;
	}
}

int AdjListGraphTest()
{
	GraphAdjList GL;
	CreateALGraph(&GL);
	return 0;
}

/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGraph G)
{
    int i, j;
    Queue<int> Q;
    for (i = 0; i < G.numNodes; i++)
        visited[i] = false;

    for (i = 0; i < G.numNodes; i++)/* 对每一个顶点做循环 */
    {
        if (!visited[i])/* 若是未访问过就处理 */
        {
            visited[i] = true;/* 设置当前顶点访问过 */
            cout << G.vexs[i] << ' '; /* 打印顶点，也可以其它操作 */
            //EnQueue(&Q, i);/* 将此顶点入队列 */
            Q.add(i);
            while (!Q.isEmpty())/* 若当前队列不为空 */
            {
                //DeQueue(&Q, &i);/* 将队对元素出队列，赋值给i */
                i = Q.remove();
                for (j = 0 ; j < G.numNodes; j++)
                {
                    /* 判断其它顶点若与当前顶点存在边且未访问过 */
                    if (G.arc[i][j] == 1 && !visited[j])
                    {
                        visited[j] = true;/* 将找到的此顶点标记为已访问 */
                        cout << G.vexs[j] << ' '; /* 打印顶点 */
                        //EnQueue(&Q, j);/* 将找到的此顶点入队列  */
                        Q.add(j);
                    }
                }
            }
        }
    }
}

/*广度优先遍历的邻接表实现 */
void BFSTraverse(GraphAdjList * GL)
{
	int i;
	EdgeNode *p;
	bool visited[GL->numNodes];
	Stack<int> * myStack = new Stack<int>();
	for (i = 0; i < GL->numNodes; i++)
		visited[i] = false;

	for (i = 0; i < GL->numNodes; i++)/* 对每一个顶点做循环 */
	{
		if (!visited[i])/* 若是未访问过就处理 */
		{
			visited[i] = true;/* 设置当前顶点访问过 */
			cout << GL->adjList[i].data << ' '; /* 打印顶点，也可以其它操作 * */
			myStack->push(i);/* 将此顶点入队列 */
			while (!myStack->isEmpty())/* 若当前队列不为空 */
			{
				i = myStack->pop();
				p = GL->adjList[i].firstedge;/* 找到当前顶点的边表链表头指针 */

				while (p)
				{
					/* 判断其它顶点若与当前顶点存在边且未访问过 * */
					if (!visited[p->adjvex])
					{
						visited[p->adjvex] = true;/* 将找到的此顶点标记为已访问 */
						cout << GL->adjList[p->adjvex].data << ' '; /* 打印顶点 * */
						myStack -> push(p->adjvex);
					}
					p = p->next;/* 指针指向下一个邻接点 */
				}
			}
		}
	}
}



/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph MG, int i)
{
    int j;
    visited[i] = true;
    cout << MG.vexs[i] << ' '; /* 打印顶点，也可以其它操作 */
    for (j = 0; j < MG.numNodes; j++)
        if (MG.arc[i][j] == 1 && !visited[j])
            DFS(MG, j);/* 对为访问的邻接顶点递归调用 */
}

/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGraph MG)
{
    int i;
    for (i = 0; i < MG.numNodes; i++)
        visited[i] = false;/* 初始所有顶点状态都是未访问过状态 */
    for (i = 0; i < MG.numNodes; i++)
        if (!visited[i])
            DFS(MG, i);/* 对未访问过的顶点调用DFS，若是连通图,只会执行一次*/
}


/* 邻接表的深度遍历操作 */
void DFS(GraphAdjList *GL, int i)
{
    EdgeNode *p;
    visited[i] = true;
    cout << GL->adjList[i].data << ' '; /* 打印顶点，也可以其它操作 */
    p = GL->adjList[i].firstedge;
    while (p)
    {
        if (!visited[p->adjvex])
            DFS(GL, p->adjvex);/* 对为访问的邻接顶点递归调用 */
        p = p->next;
    }
}

/* 邻接表的深度遍历操作 */
void DFSTraverse(GraphAdjList *GL)
{
    int i;
    for (i = 0; i < GL->numNodes; i++)
        visited[i] = false;/* 初始所有顶点状态都是未访问过状态 */

    for (i = 0; i < GL->numNodes; i++)
        if (!visited[i])
            DFS(GL, i);/* 对未访问过的顶点调用DFS，若是连通图,只会执行一次*/
}


